#include <dbg.h>
#include <gtest/gtest.h>

#include <unordered_set>
using namespace std;

class Solution {
public:
    int countPalindromicSubsequence(string s) {
        int n = s.size();

        // 构建前缀集合
        vector<unordered_set<char>> pre(n);
        for (int i = 1; i < n; ++i) {
            pre[i] = pre[i - 1];
            pre[i].insert(s[i - 1]);
        }
        dbg(pre);

        // 构建后缀集合
        vector<unordered_set<char>> suf(n);
        for (int i = n - 2; i >= 0; --i) {
            suf[i] = suf[i + 1];
            suf[i].insert(s[i + 1]);
        }
        dbg(suf);

        // 遍历中间字符，统计回文子序列
        unordered_set<string> res;
        for (int i = 1; i < n - 1; ++i) {
            for (char c : pre[i]) {     // 遍历前缀字符
                if (suf[i].count(c)) {  // 如果后缀字符中也存在该字符
                    res.insert(string(1, c) + s[i] + string(1, c));
                }
            }
        }

        return res.size();
    }
};

TEST(countPalindromicSubsequence_Test1, countPalindromicSubsequence) {
    Solution s;

    EXPECT_EQ(s.countPalindromicSubsequence("aabca"), 3);
}

TEST(countPalindromicSubsequence_Test2, countPalindromicSubsequence) {
    Solution s;

    EXPECT_EQ(s.countPalindromicSubsequence("adc"), 0);
}

TEST(countPalindromicSubsequence_Test3, countPalindromicSubsequence) {
    Solution s;

    EXPECT_EQ(s.countPalindromicSubsequence("bbcbaba"), 4);
}

int main(int argc, char** argv) {
    ::testing::InitGoogleTest(&argc, argv);
    return RUN_ALL_TESTS();
}